/*!
 Temelia - Binary Search tree samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/samples.h"
#include <temelia/binary_search_tree.h>

static void sample1()
{
	int i, N = 50, **x;
	binary_search_tree_t root, tree;

	PRINT("\n\n Sample 1 started \n\n");

	x = (int **) malloc(N * sizeof(int *));
	for (i = 0; i < N; i++)
	{
		x[i] = (int *) malloc(sizeof(int));
		x[i][0] = rand() % 1000;
	}

	root = binary_search_tree_new(x[0]);
	PRINT("Empty :  %d\nLeaf : %d\n", binary_search_tree_empty(root),
			binary_search_tree_leaf(root));

	for (i = 1; i < N; i++)
		tree = binary_search_tree_insert(root, x[i], int_compare, NULL);

	PRINT("\nIndent print : \n");
	binary_search_tree_show_indented(root, int_level_handler, NULL);

	PRINT("\nPreorder : \n");
	binary_search_tree_preorder(root, int_handler, NULL);

	PRINT("\nPostorder : \n");
	binary_search_tree_postorder(root, int_handler, NULL);

	PRINT("\nInorder : \n");
	binary_search_tree_inorder(root, int_handler, NULL);

	PRINT("\nReverse Inorder : \n");
	binary_search_tree_reverse_inorder(root, int_handler, NULL);

	PRINT("\nHeight %d\nDepth %d\n", binary_search_tree_get_height(root),
			binary_search_tree_get_depth(tree));

	PRINT("Max = %d\nMin = %d\n", *(int *) binary_search_tree_get_key(
			binary_search_tree_get_max(root)),
			*(int *) binary_search_tree_get_key(
					binary_search_tree_get_min(root)));

	PRINT("Find %d %d\n", (binary_search_tree_search(root, NULL, int_compare, NULL)
			!= NULL), (binary_search_tree_search(root, x[N / 2], int_compare, NULL)
			!= NULL));

	// Remove first 4*N/5 keys
	for (i = 0; i < 4 * N / 5; i++)
	{
		PRINT("Elimin %d\n", x[i][0]);
		binary_search_tree_remove(&root, x[i], int_compare, NULL, &tree);
		binary_search_tree_delete_node(tree);

		PRINT("\nIndent print : \n");
		binary_search_tree_show_indented(root, int_level_handler, NULL);
	}

	binary_search_tree_remove(&root, x[45], int_compare, NULL, &tree);
	binary_search_tree_delete_node(tree);

	PRINT("\nIndent print : \n");
	binary_search_tree_show_indented(root, int_level_handler, NULL);

	PRINT("\nInorder : \n");
	binary_search_tree_inorder(root, int_handler, NULL);

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	binary_search_tree_delete(root);

	PRINT("\n\n Sample 1 ended \n\n");
}

void run_binary_search_tree_samples()
{
	sample1();
}
